/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-15 10:30:43
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-15 10:30:46
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法42.数青蛙(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/minimum-number-of-frogs-croaking
 */
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        // 模拟+哈希统计
        // 遍历到roak中字符时,找一下前驱字符是否存在,不存在则出现多余字符,直接返回-1
        // 存在则继续遍历,前驱字符--,当前字符++,
        // 遍历到c字符时,找最后k字符是否存在,存在则最后一个字符--,当前字符++
        // 不存在,说明没有空闲青蛙,直接当前字符++
        // 遍历到最后,判断哈希表中所有字符是否为0,全为0返回最后k字符位置的值即可

        /******version 1, 5个if else的版本******/
        // unordered_map<char,int> hash;
        // hash.insert({{'c',0},{'r',0},{'o',0},{'a',0},{'k',0}});
        // for(const auto& ch : croakOfFrogs) {
        //     if(ch == 'c') { if(hash['k'] != 0) hash['k']--; hash['c']++;}
        //     if(ch == 'r') { if(hash['c'] != 0) {hash['c']--; hash['r']++;} else return -1;}
        //     if(ch == 'o') { if(hash['r'] != 0) {hash['r']--; hash['o']++;} else return -1;}
        //     if(ch == 'a') { if(hash['o'] != 0) {hash['o']--; hash['a']++;} else return -1;}
        //     if(ch == 'k') { if(hash['a'] != 0) {hash['a']--; hash['k']++;} else return -1;}
        // }
        // for(const auto& [k,v] : hash) 
        //     if(k != 'k' && v != 0) return -1;
        // return hash['k'];

        /******version 2, 哈希映射下标的版本******/
        string t = "croak";
        int n = t.size();
        vector<int> hash(n); // 用数组模拟哈希表
        unordered_map<char,int> index; // 存x字符及其对应的下标索引,-1即可得到前驱字符下标
        for(int i = 0; i < n; i++) index[t[i]] = i;
        for(const auto& ch : croakOfFrogs) {
            if(ch == 'c') {
                int i = index[ch]; // 'c'字符位置的下标
                if(hash[n-1] != 0) hash[n-1]--; // 判断k位置的值
                hash[i]++;
            }
            else {
                int i = index[ch]; // 当前字符位置的下标
                if(hash[i-1] == 0) return -1; // 判断前驱位置
                hash[i-1]--,hash[i]++;
            }
        }
        for(int i = 0; i < n - 1; i++) 
            if(hash[i] != 0) return -1;
        return hash[n-1];
    }
};